|
|
Watson-Crick Models for Formal Language Processing
Hammer, Jan ; Tomko, Martin (oponent) ; Křivka, Zbyněk (vedoucí práce)
This work focuses on Watson-Crick languages inspired by DNA computing, their models and algorithms of deciding the language membership. It analyzes a recently introduced algorithm called WK-CYK and introduces a state space search algorithm which is based on regular Breath-first search but uses a number of optimizations and heuristics to be efficient in practical use and able to analyze inputs of greater lengths. The key parts are the heuristics for pruning the state space (detecting dead ends) and heuristics for choosing the most promising branches to continue the search. These two algorithms have been tested with 20 different Watson-Crick grammars (40 including their Chomsky normal form versions). While WK-CYK is able to decide the language membership in a reasonable time for inputs of length of roughly 30-50 symbols and its performance is very consistent for all kinds of grammars and inputs, the state space search is usually (89-98 % of cases) more efficient and able to do the computation for inputs with lengths of hundreds or even thousands of symbols. Thus, the state space search has a potential to be a good tool for practical Watson-Crick membership testing and is a good basis to further build on and further improve the efficiency of the algorithm.
|
|
|
Inference schématu z XML dokumentu
Olšarová, Nela ; Chmelař, Petr (oponent) ; Křivka, Zbyněk (vedoucí práce)
XML je v současné době oblíbeným formátem pro výměnu a uchovávání dat. Vnitřní struktura XML dokumentů je popisována schématem, které má důležitou úlohu při manipulaci s daty. V této práci se zabýváme návrhem metody, která umožní vytvořit k množině vstupních XML dokumentů odpovídající schéma. Prozkoumali jsme stávající publikované metody, které se pokusíme vylepšit o interakci s uživatelem, která se dosud neobjevila v žádném prozkoumaném algoritmu. Při odvozování schématu využíváme formálního základu metody odvozování gramatik.
|
|
|
Final Sentential Forms and Their Applications
Kožár, Tomáš ; Kövári, Adam (oponent) ; Meduna, Alexandr (vedoucí práce)
Context-free grammars are one of the most used formal models in formal language theory. They have many useful applications, but for many applications, they lack expressive power. We introduce a final language F . When a sentential form of the context-free grammar G belongs to the F , it becomes a final sentential form. By the erasion of the nonterminals from the final sentential forms, we receive a language of G finalized by F , L(G,F) . We prove that for each recursively enumerable language L , there exists context-free grammar G , such that L = L(G,F) , with F = { w#reversal(w) | w is from {0,1}*}, where reversal(w) is a reversal of w . When a regular language is used as F , no increase in generative power compared to context-free grammars is achieved. We show multiple applications of the final sentential forms in the fields of the linguistics and bioinformatics.
|
|
|
Watson-Crick Models for Formal Language Processing
Hammer, Jan ; Tomko, Martin (oponent) ; Křivka, Zbyněk (vedoucí práce)
This work focuses on Watson-Crick languages inspired by DNA computing, their models and algorithms of deciding the language membership. It analyzes a recently introduced algorithm called WK-CYK and introduces a state space search algorithm which is based on regular Breath-first search but uses a number of optimizations and heuristics to be efficient in practical use and able to analyze inputs of greater lengths. The key parts are the heuristics for pruning the state space (detecting dead ends) and heuristics for choosing the most promising branches to continue the search. These two algorithms have been tested with 20 different Watson-Crick grammars (40 including their Chomsky normal form versions). While WK-CYK is able to decide the language membership in a reasonable time for inputs of length of roughly 30-50 symbols and its performance is very consistent for all kinds of grammars and inputs, the state space search is usually (89-98 % of cases) more efficient and able to do the computation for inputs with lengths of hundreds or even thousands of symbols. Thus, the state space search has a potential to be a good tool for practical Watson-Crick membership testing and is a good basis to further build on and further improve the efficiency of the algorithm.
|
|
|
Final Sentential Forms and Their Applications
Kožár, Tomáš ; Kövári, Adam (oponent) ; Meduna, Alexandr (vedoucí práce)
Context-free grammars are one of the most used formal models in formal language theory. They have many useful applications, but for many applications, they lack expressive power. We introduce a final language F . When a sentential form of the context-free grammar G belongs to the F , it becomes a final sentential form. By the erasion of the nonterminals from the final sentential forms, we receive a language of G finalized by F , L(G,F) . We prove that for each recursively enumerable language L , there exists context-free grammar G , such that L = L(G,F) , with F = { w#reversal(w) | w is from {0,1}*}, where reversal(w) is a reversal of w . When a regular language is used as F , no increase in generative power compared to context-free grammars is achieved. We show multiple applications of the final sentential forms in the fields of the linguistics and bioinformatics.
|
|
|
Validation and Recognition of Hierarchical Plans
Ondrčková, Simona ; Barták, Roman (vedoucí práce) ; Gemrot, Jakub (oponent)
Plánování je metoda, ve které se snažíme splnit cíl nebo cílovou úlohu vytvořením sekvence akcí, jež se nazývá plán. Hierarchické plánování je varianta plánování, která rozkládá úlohy na pod-úlohy a ty na další pod-úlohy dokud nedostaneme primitivní akce (pod-úlohy, jež se nedají rozložit). Validace plánů vezme seznam akcí a ověří zda cílová úloha je rozložitelná na tyto akce. Rozpoznávání plánů vezme prefix těchto akcí, najde ty chybějící a ověří zda se na ně dá cílová úloha rozložit. V této práci budu vytvářet dva programy. První program bude řešit problém verifikace plánů a druhý problém rozpoznávání plánů. Oba programy budou používat techniku parsování známou z oblasti gramatik.
|
|
|
Komponování hudby pomocí programovacího jazyka
Pavlín, Tomáš ; Maršík, Ladislav (vedoucí práce) ; Hajič, Jan (oponent)
Komponování hudby pomocí počítače přináší mnoho problémů a dá se zrea- lizovat mnoha různými postupy. Existující programy na skládání hudby nedávají příliš volnosti skladatelům nebo jsou příliš komplikované pro uživatele bez tech- nického zázemí. V této práci přicházíme s intuitivním programovacím jazykem navrženým pro komponování hudby. Přikládáme také interpret tohoto jazyka, který je reprezentovaný přehledným grafickým uživatelským rozhraním umožňu- jícím komponovat a produkovat hudbu i uživateli bez technického či hudebního zaměření. Program přináší nový postup, kterým mohou skladatelé komponovat hudbu, umožňuje snadné vytváření hudby například do her a dá se využít k do- provodu ke zpěvu. 1
|
|
|
Inference schématu z XML dokumentu
Olšarová, Nela ; Chmelař, Petr (oponent) ; Křivka, Zbyněk (vedoucí práce)
XML je v současné době oblíbeným formátem pro výměnu a uchovávání dat. Vnitřní struktura XML dokumentů je popisována schématem, které má důležitou úlohu při manipulaci s daty. V této práci se zabýváme návrhem metody, která umožní vytvořit k množině vstupních XML dokumentů odpovídající schéma. Prozkoumali jsme stávající publikované metody, které se pokusíme vylepšit o interakci s uživatelem, která se dosud neobjevila v žádném prozkoumaném algoritmu. Při odvozování schématu využíváme formálního základu metody odvozování gramatik.
|
host ::
RSS.